package com.chj.zhongji.class12;

// https://zhuanlan.zhihu.com/p/191627224
// https://www.nowcoder.com/questionTerminal/93bcd2190da34099b98dfc9a9fb77984?orderByHotValue=0&page=2&onlyReference=false
public class Code03_MoneyWays {

	public static int moneyWays(int[] arbitrary, int[] onlyone, int money) {
		if (money < 0) {
			return 0;
		}
		if ((arbitrary == null || arbitrary.length == 0) && (onlyone == null || onlyone.length == 0)) {
			return money == 0 ? 1 : 0;
		}

		// 任意张 的数组， 一张的数组，不可能都没有

		int[][] dparb = getDpArb(arbitrary, money);
		int[][] dpone = getDpOne(onlyone, money);
		if (dparb == null) { // 任意张的数组没有，一张的数组有
			return dpone[dpone.length - 1][money];
		}
		if (dpone == null) { // 任意张的数组有，一张的数组没有
			return dparb[dparb.length - 1][money];
		}
		int res = 0;
		for (int i = 0; i <= money; i++) {
			res += dparb[dparb.length - 1][i] * dpone[dpone.length - 1][money - i];
		}
		return res;
	}

	public static int[][] getDpArb(int[] arr, int money) {
		if (arr == null || arr.length == 0) {
			return null;
		}
		int[][] dp = new int[arr.length][money + 1];
		for (int i = 0; i < arr.length; i++) {
			dp[i][0] = 1;
		}
		for (int j = 1; arr[0] * j <= money; j++) {
			dp[0][arr[0] * j] = 1;
		}
		// 0行 0列 填完了
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j <= money; j++) {
				dp[i][j] = dp[i - 1][j];
				dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
			}
		}
		return dp;
	}

	public static int[][] getDpOne(int[] arr, int money) {
		if (arr == null || arr.length == 0) {
			return null;
		}
		int[][] dp = new int[arr.length][money + 1];
		for (int i = 0; i < arr.length; i++) {
			dp[i][0] = 1;
		}
		if (arr[0] <= money) {
			dp[0][arr[0]] = 1;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j <= money; j++) {
				dp[i][j] = dp[i - 1][j];
				dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
			}
		}
		return dp;
	}

	public static void main(String[] args) {
		{
			int[] arbitrary = new int[] { 1, 2, 3 };
			int[] onlyone = new int[] { 1 };
			int money = 5;
			System.out.println(moneyWays(arbitrary, onlyone, money));
		}

		{
			int[] arbitrary = new int[] { 87, 76, 15, 79, 53 };
			int[] onlyone = new int[] { 1, 94, 59, 30, 5 };
			int money = 100;
			System.out.println(moneyWays(arbitrary, onlyone, money));
		}
//		9
//		2
	}
}
